import java.util.Stack;

/**
 * 剑指 Offer 09. 用两个栈实现队列
 * https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
 */
public class Solutions_Offer_09 {
    public static void main(String[] args) {
//        CQueue2 queue = new CQueue2();
//        int res1 = queue.deleteHead();  // output: -1
//        System.out.println(res1);
//        queue.appendTail(5);
//        queue.appendTail(2);
//        int res2 = queue.deleteHead();  // output: 5
//        System.out.println(res2);
//        int res3 = queue.deleteHead();  // output: 2
//        System.out.println(res3);

        CQueue2 queue = new CQueue2();
        queue.appendTail(3);
        int res1 = queue.deleteHead();  // output: 3
        System.out.println(res1);
        int res2 = queue.deleteHead();  // output: -1
        System.out.println(res2);
    }
}

/**
 * 方式二：数组形式实现的两个栈，再实现队列
 */
class CQueue2 {
    private int[] stack1 = null;  // 正常的栈，实现元素的 push
    int index1 = 0;
    private int[] stack2 = null;  // 实现队列效果，保证 pop 的元素是先 push 到 stack1 中的元素
    int index2 = 0;

    public CQueue2() {
        // 最多进行 10000 次操作，即栈中最多有 9999 个元素（第一次一定为初始化对象）
        stack1 = new int[10000];
        stack2 = new int[10000];
    }

    public void appendTail(int value) {
        // 仅实现添加元素到 stack1 中
        stack1[index1++] = value;
    }

    public int deleteHead() {
        // 先将 stack1 中的全部元素弹出到 stack2中
        // 再从 stack2 中弹出元素（先进 stack1 的元素先弹出，后进 stack1 的后弹出）
        if (index1 < 1 && index2 < 1) {
            return -1;
        }
        if (index2 < 1) {
            // stack2 中没有元素时，将 stack1 中的元素全部弹出到 stack2 中
            // 将 stack1 中的全部元素弹出，记录到 stack2 中
            // 即 stack1 的栈顶元素成为了 stack2 中的栈底元素
            // stack1 中的栈底元素成为了 stack2 中的栈顶元素
            while (index1 > 0) {
                stack2[index2++] = stack1[--index1];
            }
        }
        return stack2[--index2];
    }
}

/**
 * 方式一：两个栈实现队列
 */
class CQueue {
    private Stack<Integer> stack1 = null;  // 正常的栈，实现元素的 push
    private Stack<Integer> stack2 = null;  // 实现队列效果，保证 pop 的元素是先 push 到 stack1 中的元素

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (stack2.isEmpty() && stack1.isEmpty()) {
            return -1;
        }
        if (stack2.isEmpty()) {
            // 将 stack1 中的全部元素弹出，入栈到 stack2 中
            // 即 stack1 的栈顶元素成为了 stack2 中的栈底元素
            // stack1 中的栈底元素成为了 stack2 中的栈顶元素
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}
